package Top101;

public class Test_9_24 {


    //二叉树的镜像
    public TreeNode Mirror (TreeNode pRoot) {
        if(pRoot == null) return null;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(pRoot);
        while(!queue.isEmpty()) {
            TreeNode front = queue.poll();
            TreeNode tmp = front.left;
            front.left = front.right;
            front.right = tmp;
            if(front.left != null) queue.offer(front.left);
            if(front.right != null) queue.offer(front.right);
        }
        return pRoot;
    }



    //输出二叉树的右视图
    private int preIndex  = 0;
    private int k = 0;
    int[] ret = new int[k];
    public int[] solve (int[] preOrder, int[] inOrder) {
        // 1. 根据 前序遍历和中序遍历 建立二叉树
        TreeNode root = buildChildBinaryTree(preOrder, inOrder, 0, preOrder.length - 1);
        // 2. 对二叉树进行层次遍历 ， 将每层最右边的结点 放入数组
        if (root == null) return ret;

        rightSideView(root);
        return ret;
    }
    private void rightSideView(TreeNode root) {
        Queue<TreeNode> q1 = new LinkedList<>();    //存储当前层次的结点
        Queue<TreeNode> q2 = new LinkedList<>();    //存储下一层的结点
        q1.offer(root);
        while (!q1.isEmpty() || !q2.isEmpty()) {
            ret = Arrays.copyOf(ret, k + 1);
            // 队列 q1 不为空
            if (!q1.isEmpty()) {
                while (!q1.isEmpty()) {
                    TreeNode tmp = q1.poll();
                    if (q1.isEmpty()) {
                        ret[k++] = tmp.val;
                    }
                    if (tmp.left != null) q2.offer(tmp.left);
                    if (tmp.right != null) q2.offer(tmp.right);
                }
                continue;
            }
            // 队列 q2 不为空
            while (!q2.isEmpty()) {
                TreeNode tmp = q2.poll();
                if (q2.isEmpty()) {
                    ret[k++] = tmp.val;
                }
                if (tmp.left != null) q1.offer(tmp.left);
                if (tmp.right != null) q1.offer(tmp.right);
            }
        }
    }
    private TreeNode buildChildBinaryTree(int[] preOrder, int[] inOrder, int start, int end) {
        if (start > end) return null;

        TreeNode root = new TreeNode(preOrder[preIndex]);
        // 找到 该树根结点 在中序遍历的下标
        int pivot = findRootIndex(root.val, inOrder, start, end);
        preIndex++;
        // 以 根结点的 左区间和右区间 分别建立树的 左子树和右子树
        root.left = buildChildBinaryTree(preOrder, inOrder, start, pivot - 1);
        root.right = buildChildBinaryTree(preOrder, inOrder, pivot + 1, end);
        return root;
    }
    private int findRootIndex(int key, int[] preOrder, int left, int right) {
        for (int i = left; i <= right; i++) {
            if (preOrder[i] == key) return i;
        }
        return -1;
    }
}
